import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2024-12-10
 * Time: 17:46
 */
class Solution {
    public int findKthLargest(int[] nums, int k) {
        //1:实现递归排序,传入数组，左边界，右边界，k
        int l = 0 , r = nums.length-1;
        return quickSort(nums,l,r,k);
    }


    // 把数组分成三部分
    public int quickSort(int[] nums , int l , int r , int k){
        //递归出口
        if(l == r){
            return nums[l];
        }

        //产生随机数作为下标，作为划分三部分的基准值
        Random random = new Random();
        int num = random.nextInt(r - l + 1);
        int index = num + l;
        int key = nums[index];
        int left = l-1 , right = r+1 , i = l;
        while(i < right){
            if(nums[i] > key){
                swap(nums , i , --right);
            }else if(nums[i] == key){
                i++;
            }else{
                swap(nums , i++ , ++left);//此处i++是因为 >key的值和=key的值发生了交换
            }
        }

        //根据划分的三个部分在找
        // 三个部分的区间为[l,left]  [left+1,right-1]  [right,r]
        int a = left-l+1;
        int b = right-left-1;
        int c = r-right+1;
        if(c >= k){
            return quickSort(nums,right,r,k);
        }else if(b + c >= k){
            return key;
        }else{
            return quickSort(nums,l,left,k-b-c);
        }
    }

    public void swap(int[] nums , int a , int b){
        int tem = nums[a];
        nums[a] = nums[b];
        nums[b] = tem;
    }
}
public class Test3 {
}
